{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0d467d53",
   "metadata": {},
   "source": [
    "# 4 Different Ways to Multiply 2 Matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2bf2ddd8",
   "metadata": {},
   "source": [
    "Let's establish a simple toy example as a baseline first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "21ebfb8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "A = np.array([[1.1, 1.2, 1.3],\n",
    "              [2.4, 2.5, 2.6],\n",
    "              [3.7, 3.8, 3.9]])\n",
    "\n",
    "B = np.array([[4.1, 4.2, 4.3],\n",
    "              [5.4, 5.5, 5.6],\n",
    "              [6.7, 6.8, 6.9]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d580b1e2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[19.7 , 20.06, 20.42],\n",
       "       [40.76, 41.51, 42.26],\n",
       "       [61.82, 62.96, 64.1 ]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A @ B"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9973a3fd",
   "metadata": {},
   "source": [
    "## 1) Compute row-column dot-products (the conventional way)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34d24c92",
   "metadata": {},
   "source": [
    "Each element A[i, j] in the resulting matrix A.B = AB is a dot product of row A[i, ] and column B[, j]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4cd74540",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[19.7 , 20.06, 20.42],\n",
       "       [40.76, 41.51, 42.26],\n",
       "       [61.82, 62.96, 64.1 ]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AB = np.zeros((A.shape[0], B.shape[1]))\n",
    "\n",
    "for i, row in enumerate(A):\n",
    "    for j, column in enumerate(B.T):\n",
    "        AB[i, j] = row.dot(column)\n",
    "\n",
    "AB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c04535d",
   "metadata": {},
   "source": [
    "## 2) Row-vectors times matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07563cac",
   "metadata": {},
   "source": [
    "For each column B[, j], compute the dot products between A and B[, j] to get the resulting column AB[, j]."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c7e9614",
   "metadata": {},
   "source": [
    "For each row A[i, ], compute the dot products with B to get the resulting row AB[i, ]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a7c72e7f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[19.7 , 20.06, 20.42],\n",
       "       [40.76, 41.51, 42.26],\n",
       "       [61.82, 62.96, 64.1 ]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AB = np.zeros((A.shape[0], B.shape[1]))\n",
    "\n",
    "for i, row in enumerate(A):\n",
    "    AB[i] = row.dot(B)\n",
    "    \n",
    "AB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c240fdca",
   "metadata": {},
   "source": [
    "## 3) Matrix times column-vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a9448d82",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[19.7 , 20.06, 20.42],\n",
       "       [40.76, 41.51, 42.26],\n",
       "       [61.82, 62.96, 64.1 ]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AB = np.zeros((A.shape[0], B.shape[1]))\n",
    "\n",
    "for j, column in enumerate(B.T):\n",
    "    AB[:, j] = A.dot(column[:, None]).flatten()\n",
    "    \n",
    "AB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f116aaa2-d52d-4049-ac67-a19144ffa315",
   "metadata": {},
   "source": [
    "## 4) Columns times rows"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72162938",
   "metadata": {},
   "source": [
    "## 4.1) Columns times rows with dot products (matmuls)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8bfe8ea",
   "metadata": {},
   "source": [
    "This procedure works for square matrices only:\n",
    "\n",
    "- Compute the dot-products between the columns in A and rows in B. \n",
    "- If A is $m\\times n$-dimensional, each dot-product is a $m\\times n$-dimensional matrix\n",
    "- Then sum these matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f1560377",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[19.7 , 20.06, 20.42],\n",
       "       [40.76, 41.51, 42.26],\n",
       "       [61.82, 62.96, 64.1 ]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AB = np.zeros((A.shape[1], B.shape[0]))\n",
    "\n",
    "for column_A, row_B in zip(A.T, B):\n",
    "    AB += column_A[:, None].dot(row_B[None, :])\n",
    "    \n",
    "AB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b4ae027-58ce-45e5-81ab-7babb030197d",
   "metadata": {},
   "source": [
    "## 4.2) Columns times rows with outer products\n",
    "\n",
    "For each row in A and each column in B, compute the outer product. \n",
    "The matrix AB is the sum over all these outer products."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "50f71fb9-1c27-4fdd-91ed-87264f7ca69a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[19.7 , 20.06, 20.42],\n",
       "       [40.76, 41.51, 42.26],\n",
       "       [61.82, 62.96, 64.1 ]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AB = np.zeros((A.shape[0], B.shape[1]))\n",
    "\n",
    "for column_A, row_B in zip(A.T, B):\n",
    "    AB += np.outer(column_A, row_B)\n",
    "    \n",
    "AB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75c9ea85-8a99-4442-a097-f2d83cad8cbb",
   "metadata": {},
   "source": [
    "## Bonus: The 5th way -- Block multiplication\n",
    "\n",
    "In block multiplication, we can divide up a large matrix into smaller blocks and then multiply them separately.\n",
    "\n",
    "Suppose we have the following matrix multiplication\n",
    "\n",
    "$$\n",
    "A=\\begin{bmatrix}\n",
    "1.1 & 1.2 & 1.3 & 1.4\\\\\n",
    "2.1 & 2.2 & 2.3 & 2.4\\\\\n",
    "3.1 & 3.2 & 3.3 & 3.4\\\\\n",
    "4.1 & 4.2 & 4.3 & 4.4\n",
    "\\end{bmatrix}\n",
    "B=\\begin{bmatrix}\n",
    "5.1 & 5.2 & 5.3 & 5.4\\\\\n",
    "6.1 & 6.2 & 6.3 & 6.4\\\\\n",
    "7.1 & 7.2 & 7.3 & 7.4\\\\\n",
    "8.1 & 8.2 & 8.3 & 8.4\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "AB=\\begin{bmatrix}\n",
    "33.5 & 34.0 & 34.5 & 35.0\\\\\n",
    "59.9 & 60.8 & 61.7 & 62.6\\\\\n",
    "86.3 & 87.6 & 88.9 & 90.2\\\\\n",
    "112.7 & 114.4 & 116.1 & 117.8\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "The multiplication of the blocks looks as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2840e3f0-a99d-4676-a74d-34c62199d526",
   "metadata": {},
   "source": [
    "$$\n",
    "A = \\left[\\begin{array}{ll}\n",
    "A_1 & A_2 \\\\\n",
    "A_3 & A_4\n",
    "\\end{array}\\right]\n",
    "B = \\left[\\begin{array}{ll}\n",
    "B_1 & B_2 \\\\\n",
    "B_3 & B_4\n",
    "\\end{array}\\right] \\\\ \n",
    "AB =\n",
    "\\left[\\begin{array}{ll} A_1 B_1+A_2 B_3 & A_1 B_2+A_2 B_4 \\\\\n",
    "A_3 B_1+A_4 B_3 & A_3 B_2+A_4 B_4\n",
    "\\end{array}\\right]\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d4f153c6-c698-44af-8cb3-6c177315173b",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([[1.1, 1.2, 1.3, 1.4],\n",
    "              [2.1, 2.2, 2.3, 2.4],\n",
    "              [3.1, 3.2, 3.3, 3.4],\n",
    "              [4.1, 4.2, 4.3, 4.4]])\n",
    "\n",
    "B = np.array([[5.1, 5.2, 5.3, 5.4],\n",
    "              [6.1, 6.2, 6.3, 6.4],\n",
    "              [7.1, 7.2, 7.3, 7.4],\n",
    "              [8.1, 8.2, 8.3, 8.4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "57540937-2e52-4a8a-bb87-42c9ed55966e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 33.5,  34. ,  34.5,  35. ],\n",
       "       [ 59.9,  60.8,  61.7,  62.6],\n",
       "       [ 86.3,  87.6,  88.9,  90.2],\n",
       "       [112.7, 114.4, 116.1, 117.8]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A @ B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a217d3bf-62a6-43c8-a71d-6544e1e79ea1",
   "metadata": {},
   "outputs": [],
   "source": [
    "A1, A2 = A[:2, :2], A[:2, 2:]\n",
    "A3, A4 = A[2:, :2], A[2:, 2:]\n",
    "\n",
    "B1, B2 = B[:2, :2], B[:2, 2:]\n",
    "B3, B4 = B[2:, :2], B[2:, 2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1b888d6b-5ede-4dd2-a619-298fdcbcc41c",
   "metadata": {},
   "outputs": [],
   "source": [
    "C1, C2 = A1@B1 + A2@B3, A1@B2 + A2@B4\n",
    "C3, C4 = A3@B1 + A4@B3, A3@B2 + A4@B4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "947f1463-c956-4098-882a-9ea22a51e7ef",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 33.5,  34. ,  34.5,  35. ],\n",
       "       [ 59.9,  60.8,  61.7,  62.6],\n",
       "       [ 86.3,  87.6,  88.9,  90.2],\n",
       "       [112.7, 114.4, 116.1, 117.8]])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AB = np.vstack((np.hstack((C1, C2)),\n",
    "                np.hstack((C3, C4))))\n",
    "\n",
    "AB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15be5d4a-4c1f-4c2c-ba27-7eed5875711c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
